package com.datastructure.test.reorderlistnode;

public class ReorderListNode {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next=new ListNode(2);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(4);
        ReorderListNode reorderListNode = new ReorderListNode();
        reorderListNode.reorderList(listNode);
    }

    public void reorderList(ListNode head) {
        if(head==null){
            return;
        }
        int lengthOfListNode = getLengthOfListNode(head);
        if(lengthOfListNode==2){
            return;
        }
        ListNode[] data = new ListNode[lengthOfListNode];
        for (int i = 0; i < data.length; i++) {
            data[i]=head;
            head=head.next;
        }
        for (int i = 0; i < lengthOfListNode/2; i++) {
            data[i].next=data[lengthOfListNode-i-1];
        }
        for (int j = lengthOfListNode-1; j > lengthOfListNode/2; j--) {
            data[j].next=data[lengthOfListNode-j];
        }
        head=data[0];
        ListNode cur=head;
        while (lengthOfListNode>1){
            head=head.next;
            lengthOfListNode--;
        }
        head.next=null;
        head=cur;
    }

    public int getLengthOfListNode(ListNode head){
        int length = 0;
        while (head!=null){
            length++;
            head=head.next;
        }
        return length;
    }
}

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
